#define _CRT_SECURE_NO_WARNINGS 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2010;
ll dp[N][N], w1[30], w2[30];
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	ll n = 0, m = 0; cin >> n >> m;
	string s; cin >> s;
	for (ll i = 1; i <= n; i++)
	{
		char c;
		cin >> c >> w1[c - 'a'] >> w2[c - 'a'];
	}
	for (ll i = 0; i < n; i++) dp[i][i] = 0;
	for (ll len = 2; len <= n; len++)
	{
		for (ll left = 0; left < n - len + 1; left++)
		{
			ll right = left + len - 1;
			if (s[left] = s[right])
			{
				if (len == 2)
				{
					dp[left][right] = 0;
				}
				else
				{
					dp[left][right] = dp[left + 1][right - 1];
				}
			}
			else
			{
				dp[left][right] = min(dp[left + 1][right] + min(w1[s[left] - 'a'], w2[s[left] - 'a']), dp[left][right - 1] + min(w1[s[right] - 'a'], w2[s[right] - 'a']));
			}
		}
	}
	cout << dp[0][n - 1] << endl;
	return 0;
}